#include "Heap.h"
#include <time.h>

//堆排序时间复杂度O(N + N*logN)
void HeapSort(int* a, int size)
{
	//升序 -- 建大堆
	//降序 -- 建小堆

	//建堆 -- 向上调整，时间复杂度：O(N*log(N))
	//for (int i = 0; i < size; i++)
	//{
	//	AdjustUp(a, i);
	//}

	//建堆 -- 向下调整，时间复杂度：O(N)
	//倒着调整
	//叶子节点不需要处理
	//倒数第一个非叶子节点：最后一个节点的父亲开始调整
	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, size, i);
	}

	//O(N*log(N))
	int end = size - 1;
	while (end)
	{
		//1.先交换
		Swap(&a[0], &a[end]);
		//2.再调整，选出当前大小的数组中最小数
		AdjustDown(a, end, 0);

		end--;
	}
}


void CreateNData()
{
	//造数据
	int n = 1000;
	srand((unsigned int)time(NULL));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (NULL == fin)
	{
		perror("fopen error:");
		return;
	}

	for (size_t i = 0; i < n; i++)
	{
		int x = rand() % 100000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}
void PrintTopK(int k)
{
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (NULL == fout)
	{
		perror("fopen error:");
		return;
	}

	int* kminheap = (int*)malloc(sizeof(int) * k);
	if (NULL == kminheap)
	{
		perror("malloc fail:");
		return;
	}

	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &kminheap[i]);
	}

	//建小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(kminheap, k, i);
	}

	int val = 0;
	while (!feof(fout))
	{
		fscanf(fout, "%d", &val);
		if (val > kminheap[0])
		{
			kminheap[0] = val;
			AdjustDown(kminheap, k, 0);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", kminheap[i]);
	}
	printf("\n");

}